package source.arrayAndString;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * 实现RandomizedSet 类：
 * <p>
 * RandomizedSet()      初始化 RandomizedSet 对象
 * bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
 * bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
 * int getRandom()      随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
 * 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
 */
public class RandomizedSet {

    ArrayList<Integer> arrayList = null;
    HashMap<Integer, Integer> hashMap = null;

    Random random;

    public RandomizedSet() {
        arrayList = new ArrayList<>();
        hashMap = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (hashMap.containsKey(val)) {
            return false;
        }
        int index = hashMap.size();
        hashMap.put(val, index);
        arrayList.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (hashMap.containsKey(val)) {
            Integer index = hashMap.get(val);
            Integer lastOne = arrayList.get(arrayList.size() - 1);
            arrayList.set(index, lastOne);
            arrayList.remove(arrayList.size() - 1);
            hashMap.put(lastOne, index);
            arrayList.remove(val);
            return true;
        }
        return false;
    }

    public int getRandom() {
        int r = random.nextInt(hashMap.size());
        return arrayList.get(r);
    }
}

